#include "base.h"
#include "unordered_map"
#include "unordered_set"

class Solution
{
public:
    //奇数回文
    int mirrored_half_len1(string s, int mid)
    {
        int half_len = 0;
        while (1)
        {
            int big = mid + half_len;
            int sm = mid - half_len;
            if (big < s.length() && sm >= 0)
            { //范围有效
                if (s.at(big) == s.at(sm))
                {
                    //相同有效
                    half_len++;
                }
                else
                {
                    //不同无效
                    //回退上一次有效
                    half_len--;
                    break;
                }
            }
            else
            {
                half_len--;
                break;
            }
        }
        return half_len;
    }
    //abc
    //偶数回文 先奇数后偶数，偶数即mid以及mid下一个为中心
    int mirrored_half_len2(string s, int mid)
    {
        int half_len = 0;
        while (1)
        {
            int big = mid + half_len + 1;
            int sm = mid - half_len;
            if (big < s.length() && sm >= 0)
            { //范围有效
                if (s.at(big) == s.at(sm))
                {
                    //相同有效
                    half_len++;
                }
                else
                {
                    //不同无效
                    //回退上一次有效
                    half_len--;
                    break;
                }
            }
            else
            {
                half_len--;
                break;
            }
        }
        return half_len;
    }
    string longestPalindrome(string s)
    {
        // vector<int> lens;
        // lens.resize(s.length());
        int maxlen = 0;
        int max_range_begin = 0;
        // int max_range_end = 0;

        int i = 0;

        while (i < s.length())
        {
            auto hlen1 = mirrored_half_len1(s, i);
            auto len1 = hlen1 * 2 + 1;

            auto hlen2 = mirrored_half_len2(s, i);
            auto len2 = hlen2 * 2 + 2;

            if (len1 > len2)
            {
                if (len1 > maxlen)
                {
                    maxlen = len1;
                    max_range_begin = i - hlen1;
                    // max_range_end = i + hlen1;
                }
            }
            else
            {
                if (len2 > maxlen)
                {
                    maxlen = len2;
                    max_range_begin = i - hlen2;
                    // max_range_end = i + hlen2;
                }
            }

            i++;
        }
        return s.substr(max_range_begin, maxlen);
    }
};

void main()
{
    Solution sol;
    vector<int> a1 = {1, 2};
    vector<int> a2 = {3, 4};

    auto a = sol.findMedianSortedArrays(a1, a2);
}